package net.tp.algo.knapsack;

/**
 *
 * <p>Bounded Knapsack Problem.</p>
 *
 * @author Trung Phan
 *
 */
public class BoundedKnapsack {

    public static int[] find(int[] sizes, double[] values, int[] bounds, int capacity) {

        int N = sizes.length;

        double[][] M = new double[N+1][capacity+1];
        int[][] traces = new int[N+1][capacity+1];

        for (int i = 1; i <= N; i++) {
            for (int c = 1; c <= capacity; c++) {
                M[i][c] = M[i-1][c];

                for (int q = 1; q <= bounds[i-1] && c >= sizes[i-1] * q; q++) {
                    if (M[i][c] < values[i-1] * q + M[i-1][c - sizes[i-1] * q]) {
                        M[i][c] = values[i-1] * q + M[i-1][c - sizes[i-1] * q];
                        traces[i][c] = q;
                    }
                }
            }
        }

        int[] result = new int[N];
        int c = capacity;
        for (int i = N; c > 0; i--) {
            if (traces[i][c] > 0) {
                result[i-1] = traces[i][c];
                c -= sizes[i-1] * traces[i][c];
            }
        }

        return result;
    }


}
